package org.codetranslators.common;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Vector;

import org.codetranslators.compiler.intermrep.AssemblyInstruction;
import org.codetranslators.compiler.intermrep.CJump;
import org.codetranslators.compiler.intermrep.Jump;
import org.codetranslators.compiler.intermrep.LabelInstr;

public class CFGLinearizationDFS extends DepthFirstSearch{
	
	public static final String tab = "\t";
	public static final String newLine = "\r\n";
	
	private Vector<AssemblyInstruction> result;
	private ControlFlowGraph controlFlowGraph;
	
	private HashSet<Node> visitedNodes;
	private HashMap<Edge, Boolean> edgeVsVisitStatus;
	
	private ControlFlowNode lastAddedNode;
	
	private boolean lastNodeAdded;
	
	public Object execute(DiGraph graph, Node startNode){
		super.execute(graph, startNode);
		
		controlFlowGraph = (ControlFlowGraph) graph;
		result = new Vector<AssemblyInstruction>();
		
		edgeVsVisitStatus = new HashMap<Edge, Boolean> ();
		visitedNodes = new HashSet<Node>();
		lastNodeAdded = false;
		visit(startNode);
		result.addAll(((ControlFlowNode)startNode).getInstructions());
		
		int numEdges = graph.getNumEdges();
		for(int i = 0; i < numEdges; i++)
		{
			Boolean visited = new Boolean(false);
			Edge edge = graph.getEdge(i);
			edgeVsVisitStatus.put(edge, visited);
		}
		
		return traverse(startNode);
	}
	
	
	public boolean isVisited(Edge edge) {
		Boolean visited = (Boolean) edgeVsVisitStatus.get(edge);
		return visited.booleanValue();
	}
	
	public  boolean isVisited(Node node){
		if(visitedNodes.contains(node)) return true;
		return false;
	}
	
	public void visit(Edge edge){
		edgeVsVisitStatus.put(edge, new Boolean(true));
	}
	
	public void visit(Node node){
		visitedNodes.add(node);		
	}
	
	public  boolean isDone(){
		if(visitedNodes.size() == controlFlowGraph.getNumNodes()){
			return true;
		}
		return false;
	}
	
	public  void traverseDiscovery(Node nextNode, Node node){
		ControlFlowNode nextCFNode = (ControlFlowNode) nextNode;
		
		// We add the instructions in the end node to the end of the 
		// instructions; so if the nextNode is the end node, return
		if(nextCFNode == controlFlowGraph.getEndNode()){ 
			visit(nextCFNode);
			return;
		}
		
		ControlFlowNode cfNode = (ControlFlowNode) node;
		
		Vector<AssemblyInstruction> instrsInSrc = cfNode.getInstructions();
		// If the source node has not been visited, add the instructions
		// in the source node now
		if(!isVisited(cfNode)){
			result.addAll(instrsInSrc);
		}
		
		Vector<AssemblyInstruction> instrsInDest = nextCFNode.getInstructions();
		
		AssemblyInstruction lastInstrInResult = result.elementAt(result.size() -1);
		AssemblyInstruction firstInstrInDest = instrsInDest.elementAt(0);
		LabelInstr lbl = (LabelInstr) firstInstrInDest;
		int typeOfLastInstrInResult = lastInstrInResult.getType();
		if(typeOfLastInstrInResult == AssemblyInstruction.JUMP){ // Last inst in the src node is a jump
			String jmpToLbl = ((Jump)lastInstrInResult).getLabel();
			if(jmpToLbl.equals(lbl.getLabelStr()))
				result.remove(lastInstrInResult);
		}
		else if(typeOfLastInstrInResult == AssemblyInstruction.CJUMP){
			CJump cjump = (CJump) lastInstrInResult;
			String trueLbl = cjump.getTrueLabel();
			if(trueLbl.equals(lbl.getLabelStr())){
				cjump.setConverse();
			}
		}
		else{
			addJump(lbl);
		}
		
		result.addAll(instrsInDest);
		
		// Update the last added Node
		lastAddedNode = nextCFNode;
	}
	
	/**
	 * Adds a jump statement to the instructions in the node added PREVIOUSLY. Does
	 * so only if required.
	 * @param currentLabel
	 */
	private void addJump(LabelInstr currentLabel){
		// The last added node must have at least one successor
		Vector<Node> children = lastAddedNode.getSuccessors();
		ControlFlowNode child = (ControlFlowNode)children.elementAt(0);
		Vector<AssemblyInstruction> instrsInChildNode = child.getInstructions();
		
		String lblOfNextNode = ((LabelInstr) instrsInChildNode.elementAt(0)).getLabelStr();
		String currentLabelString = currentLabel.getLabelStr();
		if(!lblOfNextNode.equals(currentLabelString)){
			// Add a jump to the child node
			String newLblStr = tab + "j " + lblOfNextNode + newLine;
			Jump newJump =  new Jump(newLblStr, lblOfNextNode);
			result.addElement(newJump);
		}
	}
	
	public  void traverseBack(Edge edge, Node node){
		
	}
	
	public void finishVisit(Node node) {
		// Add the instructions in the end node if all nodes have been discovered
		if(visitedNodes.size() == controlFlowGraph.getNumNodes()){
			if(!lastNodeAdded){
				ControlFlowNode endNode = controlFlowGraph.getEndNode();
				Vector<AssemblyInstruction> endNodeIns = endNode.getInstructions();
				
				addJump((LabelInstr)endNodeIns.elementAt(endNodeIns.size() -1));
				result.addAll(endNode.getInstructions());
				lastNodeAdded = true;
			}
		}
	}
	
	public Object getResult(){
		return result;
	}
}
